package com.qch.edu.Tree.DiguiTaolu;

import com.qch.edu.Tree.Node;

/**
 * @Author qch
 * @Date 2021/3/13
 * 题目：给定以课二叉树的头节点head,返回这颗二叉树是不是平衡二叉树
 * 1）左树平衡
 * 2）右树平衡
 * 3）左树高度和右树高度差不超过1
 *
 * * 以X为头的节点
 *  * 潜在信息：左子树信息和右子树信息可以得到
 *
 *  平衡树：每一颗子树，左树的高度和右树的高度差不超过1
 */
public class PinghengTree {
    public static class Node {
        private int value;        //节点的值
        private Node node;        //此节点，数据类型为Node
        private Node left;        //此节点的左子节点，数据类型为Node
        private Node right;       //此节点的右子节点，数据类型为Node
        public Node(int data){
            this.value=data;
        }
    }
    public static class Info{
        public boolean isBalanced;
        public int height;
        public Info(boolean b,int h){
            isBalanced=b;
            height=h;
        }
    }
    public static Info process2(Node X){
        if (X==null)
        {
            return new Info(true,0);
        }
        Info leftInfo = process2(X.left);
        Info rightInfo = process2(X.right);
        int height=Math.max(leftInfo.height,rightInfo.height)+1;//左右树中最大高度+头节点1
        boolean isBalance=true;
        if(!leftInfo.isBalanced||!rightInfo.isBalanced||Math.abs(leftInfo.height-rightInfo.height)>1){
            isBalance=false;
        }
        return new Info(isBalance,height);
    }

    public static boolean isBalance2(Node head){
        return process2(head).isBalanced;
    }
    public static void main(String[] args) {

    }
}
